package 单周赛.history;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 *
 */
public class 第334场单周赛 {

    public static void main(String[] args) {

        leftRigthDifference(new int[]{10, 4, 8, 3});

        divisibilityArray("998244353", 3);

        System.out.println(maxNumOfMarkedIndices(new int[]{42, 83, 48, 10, 24, 55, 9, 100, 10, 17, 17, 99, 51, 32, 16, 98, 99, 31, 28, 68, 71, 14, 64, 29, 15, 40}));

        System.out.println(minimumTime(new int[][]{{0, 1, 3, 2}, {5, 1, 2, 5}, {4, 3, 8, 6}}));

    }

    /**
     * 前缀和
     */
    public static int[] leftRigthDifference(int[] nums) {
        int[] leftSum = new int[nums.length + 1];
        int[] rightSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            leftSum[i + 1] = leftSum[i] + nums[i];
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            rightSum[i] = rightSum[i + 1] + nums[i];
        }

        int[] ans = new int[nums.length];

        for (int i = 0; i < ans.length; i++) {

            ans[i] = Math.abs(leftSum[i] - rightSum[i + 1]);

        }
        return ans;
    }

    /**
     * 求大数是否可以整除某个小数
     */
    public static int[] divisibilityArray(String word, int m) {
        char[] chars = word.toCharArray();
        int[] ans = new int[word.length()];
        long mod = 0;
        for (int i = 0; i < ans.length; i++) {
            mod = (mod * 10 + (chars[i] - '0')) % m;
            if (mod == 0) {
                ans[i] = 1;
            }
        }
        return ans;
    }

    /**
     * 排序+双指针
     */
    public static int maxNumOfMarkedIndices(int[] nums) {
        if (nums.length == 1) return 0;
        int cnt = 0;
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        int left = nums.length % 2 == 0 ? nums.length / 2 - 1 : nums.length / 2, right = nums.length - 1;

        while (right > 0) {
            while (left >= 0 && (visited[left] || nums[left] * 2 > nums[right])) {
                left--;
            }
            if (left == -1) {
                return cnt;
            }
            cnt += 2;
            visited[left] = true;
            visited[right] = true;
            left--;

            while (right > 0 && visited[right]) {
                right--;
            }
        }
        return cnt;
    }

    private static int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    /**
     * 广度优先搜索（内存溢出）
     */
    public static int minimumTime(int[][] grid) {
        int time = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{0, 0});

        while (!queue.isEmpty()) {
            time++;
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.pollFirst();

                for (int[] direct : direction) {
                    int nextRow = cur[0] + direct[0];
                    int nextColumn = cur[1] + direct[1];
                    if (nextRow >= 0 && nextRow < grid.length &&
                            nextColumn >= 0 && nextColumn < grid[0].length &&
                            grid[nextRow][nextColumn] <= time) {

                        if (nextRow == grid.length - 1 && nextColumn == grid[0].length - 1) {
                            return time;
                        }
                        grid[nextRow][nextColumn] = -1;
                        queue.addLast(new int[]{nextRow, nextColumn});
                    }
                }
            }
        }
        return -1;
    }

}
